#pragma once

#include <iostream>
#include <vector>
using namespace std;

namespace ssy
{
	template<class K>
	struct hash_func
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct hash_func<string>
	{
		size_t operator()(const string& str)
		{
			size_t ret = 0;
			for (auto& ch : str)
			{
				ret *= 131;
				ret += ch;
			}
			return ret;
		}
		
	};

	template<class K, class V>
	struct hash_node
	{
		pair<K, V> _kv;
		hash_node<K, V>* _next;

		hash_node(const pair<K, V>& kv)
			: _kv(kv)
			, _next(nullptr)
		{
			
		}
	};

	template<class K, class V, class HashFunc = hash_func<K>>
	class hash_table
	{
	public:
		typedef hash_node<K, V> Node;

		hash_table()
		{
			_table.resize(10);
		}

		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
			{
				return false;
			}

			HashFunc hf;
			if (_n == _table.size())
			{
				size_t newsize = 2 * _table.size();
				vector<Node*> newtable;
				newtable.resize(newsize);

				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						size_t hashi = hf(cur->_kv.first) % newsize;
						
						cur->_next = newtable[hashi];
						newtable[hashi] = cur;

						cur = next;
					}
					_table[i] = nullptr;
				}

				_table.swap(newtable);
			}

			int hashi = hf(kv.first) % _table.size();
			
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			
			++_n;

			return true;
		}

		Node* find(const K& key)
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					if (cur->_kv.first == key)
					{
						return cur;
					}
					else
					{
						cur = cur->_next;
					}
				}
			}
			return nullptr;
		}

		bool erase(const K& key)
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				Node* prev = nullptr;
				while (cur)
				{
					if (cur->_kv.first == key)
					{
						if (prev == nullptr)
						{
							_table[i] = cur->_next;
						}
						else
						{
							prev->_next = cur->_next;
						}

						delete cur;
						return true;
					}
					else
					{
						prev = cur;
						cur = cur->_next;
					}
				}
			}

			return false;
		}

		void print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << " : " << cur->_kv.second;
					cur = cur->_next;
				}
				cout << " NULL " << endl;
			}
		}

	private:
		vector<Node*> _table;
		size_t _n = 0;
	};

}